package week_8;

import week_8.jsjf.ArrayBinaryTree;
import week_8.jsjf.exceptions.EmptyCollectionException;

public class BigArrayHeap<T> extends ArrayBinaryTree<T> implements BigHeapADT<T>
{
    /**
     创造一个空的大顶堆。
     */
    public BigArrayHeap()
    {
        super();
    }

    /**
     添加元素在大顶堆中。
     */
    public void addElement(T obj)
    {
        if (count == tree.length)
            expandCapacity();

        tree[count] = obj;
        count++;
        modCount++;

        if (count > 1)
            heapifyAdd();
    }

    /**
     * 对插入后的大顶堆进行排序的方法。
     */
    private void heapifyAdd()
    {
        T temp;
        int next = count - 1;

        temp = tree[next];

        while ((next != 0) &&
                (((Comparable)temp).compareTo(tree[(next-1)/2]) > 0))
        {
            tree[next] = tree[(next-1)/2];
            next = (next-1)/2;

        }
        tree[next] = temp;

    }
    public void sort() {
        int i = count;
        while(i>0){
            removeMax();
            i--;
            System.out.println("每轮排序结果" + toString());
        }
    }



    /**
     删除最大堆中最大值的方法
     */
    public T removeMax() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayHeap");

        T maxElement = tree[0];
        tree[0] = tree[count-1];

        heapifyRemove();
        tree[count-1] = maxElement;
        count--;
        modCount--;

        return maxElement;
    }

    /**
     在删除堆中最大值后进行排序的方法
     */
    private void heapifyRemove()
    {
        T temp;
        int node = 0;
        int left = 1;
        int right = 2;
        int next;

        if ((tree[left] == null) && (tree[right] == null))
            next = count;
        else if (tree[right] == null)
            next = left;
        else if (((Comparable)tree[left]).compareTo(tree[right]) > 0)
            next = left;
        else
            next = right;
        temp = tree[node];

        while ((next < count) &&
                (((Comparable)tree[next]).compareTo(temp) > 0))
        {
            tree[node] = tree[next];
            node = next;
            left = 2 * node + 1;
            right = 2 * (node + 1);
            if ((tree[left] == null) && (tree[right] == null))
                next = count;
            else if (tree[right] == null)
                next = left;
            else if (((Comparable)tree[left]).compareTo(tree[right]) > 0)
                next = left;
            else
                next = right;
        }
        tree[node] = temp;
    }


    public T findMax() throws EmptyCollectionException
    {
        if (isEmpty())
            throw new EmptyCollectionException("ArrayHeap");

        return tree[0];
    }

    public String toString(){
        String str="";
        int i = 0;
        while(i<8) {
            str += tree[i] + " ";
            i++;
        }
        return str;
    }
}
